package com.ztom.daily.n2022.m4;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 * O(1)时间插入、删除和获取随机元素
 * <p>
 * https://leetcode-cn.com/problems/insert-delete-getrandom-o1/
 *
 * @author ZhangTao
 */
public class Day13RandomizedSet {

    class RandomizedSet {

        private List<Integer> list;
        private Map<Integer, Integer> map;
        private Random random;

        public RandomizedSet() {
            this.list = new ArrayList<>();
            this.map = new HashMap<>();
            this.random = new Random();
        }

        public boolean insert(int val) {
            if (map.containsKey(val)) {
                return false;
            }
            int index = list.size();
            list.add(val);
            map.put(val, index);
            return true;
        }

        public boolean remove(int val) {
            if (!map.containsKey(val)) {
                return false;
            }
            // 要删除的元素角标
            Integer index = map.get(val);
            // 最后一个元素
            Integer last = list.get(list.size() - 1);
            // 先把最后一个元素放到要删除的位置
            list.set(index, last);
            map.put(last, index);
            // 然后删除最后一个元素
            list.remove(list.size() -1);
            map.remove(val);
            return true;
        }

        public int getRandom() {
            return list.get(random.nextInt(list.size()));
        }
    }
}
